# 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
#  你可以假设除了数字 0 之外，这两个数字都不会以零开头。
#
#  示例1：
# 输入：l1 = [7,2,4,3], l2 = [5,6,4]
# 输出：[7,8,0,7]
#
#  示例2：
# 输入：l1 = [2,4,3], l2 = [5,6,4]
# 输出：[8,0,7]
#
#  示例3：
# 输入：l1 = [0], l2 = [0]
# 输出：[0]

from com.example.linked.common import *


class Solution:
    """
    解法二:栈
    链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，考虑使用栈：
    把所有数字压入栈中，再依次取出相加(结果头插)
    """

    def addTwoNumbers2(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1, stack2 = [], []
        tmp = l1
        while tmp is not None:
            stack1.append(tmp.val)
            tmp = tmp.next

        tmp = l2
        while tmp is not None:
            stack2.append(tmp.val)
            tmp = tmp.next

        res = ListNode(-1)
        carry = 0
        while len(stack1) > 0 or len(stack2) > 0 or carry != 0:
            num1 = stack1.pop() if (len(stack1) > 0) else 0
            num2 = stack2.pop() if (len(stack2) > 0) else 0
            sum = num1 + num2 + carry
            carry = sum // 10
            tmp = ListNode(sum % 10)
            tmp.next = res.next
            res.next = tmp

        return res.next

    """
    解法一:
    先翻转链表再相加(计算结果头插)
    """

    def addTwoNumbers1(self, l1: ListNode, l2: ListNode) -> ListNode:
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)
        tmp1, tmp2, res = l1, l2, ListNode(-1)
        carry = 0

        while (tmp1 is not None) or (tmp2 is not None):
            var1 = tmp1.val if tmp1 is not None else 0
            var2 = tmp2.val if tmp2 is not None else 0
            sum = (var1 + var2 + carry) % 10
            carry = (var1 + var2 + carry) // 10
            tmp1 = tmp1.next if tmp1 is not None else None
            tmp2 = tmp2.next if tmp2 is not None else None
            tmp = ListNode(sum)
            tmp.next = res.next
            res.next = tmp

        if carry != 0:
            tmp = ListNode(carry)
            tmp.next = res.next
            res.next = tmp
        return res.next

    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        tmp = head  # 保存next的位置，主要是为了不丢失下一次要访问的位置
        cur = head  # 用于迭代存储本次需要翻转的节点
        while tmp is not None:
            tmp = tmp.next
            cur.next = pre  # 翻转链表
            pre = cur
            cur = tmp
        return pre

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        return self.addTwoNumbers2(l1, l2)


# test code
if __name__ == "__main__":
    l1 = getListNode(7, 2, 4, 3)
    l1 = ListNode(7)
    l1.next = ListNode(2)
    l1.next.next = ListNode(4)
    l1.next.next.next = ListNode(3)

    l2 = getListNode(5, 6, 4)

    res = Solution().addTwoNumbers(l1, l2)
    vistListNode(res)
